package cn.itcast.com.homework.day826;

/**
 * Created by 郭浩 on 2020/8/26 19:40
 * 快排
 */
public class test {
    public static void main(String[] args) {
        int[] s = {3,4,1,2,7,11,8};
        quick_sort(s,0,6);
        for (int i = 0; i < s.length; i++) {
            System.out.println(s[i]);
        }

    }
    public static void quick_sort(int[] s, int l, int r)
    {
        if (l < r)
        {
            //将中间的这个数和第一个数交换
            int i = l, j = r, x = s[l];
            while (i < j)
            {
                // 从右向左找第一个小于x的数
                while(i < j && s[j] >= x)
                    j--;
                if(i < j)
                    s[i++] = s[j];

                // 从左向右找第一个大于等于x的数
                while(i < j && s[i] < x)
                    i++;
                if(i < j)
                    s[j--] = s[i];
            }
            s[i] = x;
            //递归
            quick_sort(s, l, i - 1);
            quick_sort(s, i + 1, r);
        }
    }
}
